Bài thực hành 7: Hàng ưu tiên và Cây nhị phân

Chúng ta đang xây dựng gì 🎯

  • Cấu trúc dữ liệu: Một Hàng ưu tiên (PQ).
    • Đó là một kiểu dữ liệu trừu tượng giống như danh sách hay hàng đợi, nhưng có một điểm khác biệt.
    • Mỗi mục đều có một "ưu tiên" (một khóa).
    • Khi bạn "lấy ra," bạn luôn luônluôn nhận được mục có ưu tiên cao nhất.
  • Các thao tác:
    • 1. push(k)
    • 2. peek()
    • 3. pop()
  • Cách triển khai:Chúng ta sẽ sử dụng một Cây nhị phân tối đại.
  • Tại sao lại dùng cây heap?Nó rất hiệu quả! Cây heap mang lại cho chúng ta:
    • push: O(log N)
    • pop: O(log N)
    • peek: O(1)

Cây nhị phân tối đại là gì?

Một cây nhị phân với hai quy tắc đơn giản:

1. Tính chất hình dạng

Đó là một cây nhị phân hoàn chỉnh. Tất cả các cấp đều đầy, ngoại trừ *có thể* cấp cuối cùng, được điền từ trái sang phải. Không có khoảng trống.

Nhấp vào một nút lá để xóa

2. Tính chất cây nhị phân tối đại

Khóa của cha phải là lớn hơn hoặc bằngkhóa của các con. Điều này đảm bảo rằng phần tử có giá trị lớn nhất luôn nằm ở gốc. lớn nhấtphần tử luôn nằm ở gốc.

Lưu trữ cây 💾

Vì cây là hoàn chỉnh, ta có thể lưu trữ nó một cách hoàn hảo trong một mảng đơn giản.

Toán học chỉ số (bắt đầu từ 0)

Với một nút tại chỉ số i:

  • Cha(i - 1) // 2
  • Con trái2 * i + 1
  • Con phải2 * i + 2

Lời khuyên:Học thuộc các công thức này! Chúng chính là chìa khóa để di chuyển trong "cây" bên trong mảng của bạn.